1780E - Josuke and Complete Graph - CodeForces Solution

// Mtaylor
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define endl '\n';
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
}
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
typedef long long ll;
const int N = 3e5 + 5;

ll l, r;
bool ok(ll u) {
    ll nx = l + (u - l % u) % u;
    if (nx <= r && nx + u <= r) {
        return 1;
    }
    return 0;
}

void test_case() {
    cin >> l >> r;
    ll ans = 0;
    if (r / 2 >= l) {
        ans += r / 2 - l + 1;
    }
    ll lf = 1;
    while (lf < l) {
        ll a = lf;
        ll b = l - 1;
        while (a < b) {
            ll md = (a + b + 1) / 2;
            if ((l + md - 1) / md != (l + lf - 1) / lf) {
                b = md - 1;
            } else {
                a = md;
            }
        }
        ll rg = a;
        ll f = (l + lf - 1) / lf;
        ll ub = min(rg, r / (f + 1));
        if (ub >= lf) ans += ub - lf + 1;
        lf = rg + 1;
    }
    cout << ans << endl;
}

int main() {
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        test_case();
    }
    return 0;
}